In ATM (ATM=Asynchronous Transfer Mode) information is transferred in cells consisting of headers of 5 bytes each and of an information part of 48 bytes. Header fields are e.g. VPI (Virtual Path Indicator) and VCI (Virtual Channel Indicator). The standard size of cells allows quick connecting of the cells. Cell channelling is asynchronous and time-divided. Before the data transfer step proper, a virtual connection is formed through the network, and the cells generated by the user are routed through this virtual connection. Upon completion of the data transfer, disconnection is performed.
A virtual bus level connection and a virtual channel level connection can be distinguished in the network. In the VP (Virtual Path) connection virtual buses are connected between transfer connections. On a virtual bus e.g. a direct connection may be formed between two exchanges, even though the connection passes through other exchanges. The virtual bus contains several virtual channels and in the VC (Virtual Channel) connection virtual channels are connected between virtual buses.
Connection Admission Control or CAC is a set of procedures intended to limit the load caused by sources wishing to enter the network and the load of internal connections in such a way that a guaranteed QOS (Quality of Service) is preserved for each existing connection. The equivalent capacity required by the virtual bus or physical connection must be defined computationally in the connection admission control. If all traffic descriptors of a requested connection are known, the only duty is to determine how much standby capacity there is in the virtual path or physical connection for admission of a new connection without any resulting loss for existing connections.
It is agreed at present that a traffic source requesting connection shall always state at least its PCR (Peak Cell Rate), its SCR (Sustainable Cell Rate), its BT (Burst Tolerance) and the CDVT (Cell Delay Variation Tolerance). In addition, the probability P(on) with which it transmits can be estimated.
However, it is often the case that the "band width" or capacity required by the requested connection is not standard and only depending on the traffic descriptors of this concerned connection, but it depends on the character and volume of the traffic of other virtual channels, which channels share the same virtual bus and physical link. Besides, it is next to impossible to get to know the exact traffic descriptors of sources: it is difficult to characterise the traffic brought about by a work station working in a multiprocessor environment and how the traffic varies with the application.
The equivalent capacity of a virtual channel is that lowest capacity which is needed to ensure QOS for all virtual connections sharing the same virtual bus, should a new request be admitted. Since the equivalent capacity depends on the traffic of all connections, it is difficult to compute the necessary standby capacity and to determine whether there is sufficient standby capacity or not.
FIGS. 1A and 1B are used to illustrate how difficult it is to determine equivalent capacity. It is assumed that each traffic source has the same traffic descriptors and they transmit cells in bursts: in the "on" state, the source generates information at standard bit rate R bit/s, while in the "off" state it does not generate information, top part of the figure. ATM cells are generated from the information when the source is in the "on" state, bottom part of FIG. 1A, so in this state the rate of ATM cells is the said R bit/s. At the ATM access gate the reception rate of cells is S. Thus, the continuous flow of cells generated by the source in the "on" state is seen at the access gate of the network as a quasi periodic sequence of ATM cells while the average time of arrival is one cell for each S/R time slot. In the off state no cells will arrive.
The following is a description of multiplexing of N different sources into a common virtual bus, FIG. 1B. The input gate has a buffer 11, which stores such cells in a queue which can not be forwarded at once to the output link having a finite capacity C. If the buffer size is infinite, then the minimum rate of the output link must be equal to the mean rate of cells arriving from N sources, which is N.times.R.times.P(on), wherein P(on) is the probability of cells being transmitted by the source. If the buffer is very small, it is safest to use a top rate as the effective band for the source, which would hereby also be an unconditional top limit for the reserved capacity. Thus, the equivalent capacity required for multiplexing N sources at the same time maintaining only a small buffer overflow possibility, N.times.R (equivalent capacity is N times the top rate of the source). It follows from these, that when using a buffer of a moderate size the equivalent capacity needed for multiplexing N sources is somewhere in a range between N.times.R.times.P(on) and N.times.R.
It is very difficult to determine the equivalent capacity when traffic of different types and having a complicated source model is multiplexed into the same virtual channel.
The connections needed by many traffic sources are bursts, whereby the transfer capacity required at some moment is high while the capacity required at another moment is small. Bursts may be described as a phenomenon where a set of cells (a burst) arrives at short intervals and the following set (burst) arrives after a relatively long time. Since different connections need different capacities and the need varies quickly, statistic channelling is used in an ATM network. The statistic characteristics of burst-like traffic sources is utilised in the channelling: when combining a large set of traffic sources the combined traffic will behave in a more stable manner than individual sources and although the transmission speed of individual sources varies, the combined transmission speed of mutually independent individual sources is almost standard. By using statistic channelling it is possible with the same resources to serve more connections, that is, the utilisation rate of the network can be raised.
In spite of statistic channelling, congestion and overloads will occur in the network. Congestion in a broadband network means such a state of network elements, wherein the network is unable to fulfil required performance objectives. Overload again means a situation where performance objectives can still be achieved even though the performance has decreased. Congestion and overload are caused both by unpredictable statistic variations in the traffic and by failure situations occurring in the network. Since it is still impossible to know with sufficient exactness network services, the volume of traffic brought about by them and the exact characteristics of traffic sources, the occurrence of congestion situations is unavoidable in the network. The purpose of traffic control and congestion situation control is to protect the network and the user so that the desired quality of network service is achieved. Traffic control exists when the activity is preventive and it is intended to prevent the occurrence of congestion situations. Control of congestion situations for its part reacts to congestion situations observed in the network. Most significant from the viewpoint of service quality are such traffic control functions which will prevent beforehand congestion situations from occurring. The CAC (Connection Admission Control) belonging to these functions is the most important preventive traffic control method. Functions relating to connection admission control attend to routing of connections, they make decisions on connection admission, they reserve the necessary resources and they set traffic parameters monitored by UPC (Usage Parameter Control) and by NPC (Network Parameter Control). The simplified result of CAC is "yes" or "no"--the new virtual connection can be either admitted or not admitted.
The literature presents several different methods of implementing connection admission control, CAC. In these the criterion is the probability either of losing cells or of filling the buffer and they are based either on traffic parameters stated by the user according to definitions of the ITU or ATM-Forum or on traffic measurements taking place in the network junction. It is possible to estimate the quality of service or the capacity requirement which can be expected according to traffic parameters either with the aid of pre-computed tables as in so-called indirect methods or by doing computing in real time based on traffic parameters of the connection, on the characteristics of other traffic and on available resources, as is done in so-called direct methods. Traffic parameters defined by ATM-Forum and indicating the traffic of the connection are: the peak cell rate (PCR), sustainable cell rate (SCR), maximum burst size (MBS), cell delay variation tolerance (CDVT) and minimum cell rate (MCR).
In measurements it is possible to measure cells arriving within a fixed period of time: the peak rate, the sustainable rate, the maximum number of arrivals, the average value and the variance. Based on these one can estimate the probability of bursts by observing the traffic in connections or one can estimate the probability of cell losses.
The method of reserving capacity based on the peak rate of the traffic source is a simple method very suitable for sources transmitting at a standard rate.
In the method based on convolution, the characteristics of all traffic sources are used for calculating the distribution of band widths of connections and this is compared with available resources. Due to the great number of variables, computing is heavy when there are many connections. In theory, this method gives an accurate result.
In the method based on effective capacity, capacity is reserved according to the traffic source's effective capacity which is estimated in one way or another. However, it is not possible to define any exact capacity for the connection, because the size of the effective band depends not only on traffic source characteristics and on the desired cell loss ratio but also on multiplexer and background traffic characteristics.
Methods based on effective variance use the sustainable rate of connections and the sustainable rate variance as their criteria. These methods give a slightly better resource utilisation ratio than methods using effective capacity.
In two-level methods quick decisions on connection admission are made in real time at the lower level by using some suitable algorithm. The upper level need not function for each call in real time, so it may at times determine the correctness of the lower level function with the aid of a more precise model.
An admission method which has been proposed for use in the case of a buffer-less queue is presented in the publication Performance Evaluation and Design of Multiservice Networks, COST 244 Final Report Commission of European Communities, Information Technologies and Sciences, Luxembourg, 1992, pages 108-110 and 154-155. It is based on a mathematical method called Large Deviation Approximation which is known from other contexts. The idea of the application of the referred method is to make sure that the probability that the sum of momentary arrival rates of cells multiplexed from sources will exceed the output link capacity is less than or equal to the permissible probability of cell loss.
Despite the fact that several different theoretical models have been proposed for implementation of connection admission control, CAC, application of them in practice has proved difficult due to the necessary complex computing. Most CAC models are concerned with the case of one buffer, and so far no such feasible admission model for a connection with several buffers has been presented wherein there are ATM cells with different priority in the buffers. The presented models with several buffers do not allow any division of capacity between buffers but parallel buffers are implemented like several individual buffers. In other words, if a buffer does not use all of its capacity, this is not automatically available to others.
It is an objective of the present invention to find a method of connection admission control CAC, which is as simple as possible and which is especially suitable for use together with burst-like sources when their cells are directed to a junction provided with a buffer and which will make sure a high admission of the requested connection. Decision-making should be prompt and require a minimum of real time computing.
The established objective is achieved with the definitions presented in the independent claims.